a = 1
b = 1
k = 2

def check(s = set()):
    if s.__len__() != 9:
        return False
    for x in s:
        if x == '0':
            return False
    return True

def findcandi():
    ans = []
    a = 1
    b = 1
    k = 2
    while True:
        k = k + 1
        c = (a + b) % 1000000000
        a = b
        b = c
        s = set(str(c))
        if (check(s)):
            ans.append(k)
        if ans.__len__() == 1000:
            break
    return ans

# print(findcandi())
candi = findcandi()
for stone in candi:
    print(stone)
    while k < stone:
        k = k + 1
        c = a + b
        a = b
        b = c
    s = set(str(c)[:9])
    if (check(s)):
        print(k)
        break

# while True:
#     k = k + 1
#     c = a + b
#     a = b
#     b = c
#     s = str(c)
#     set1 = set(s[:9])
#     set2 = set(s[-9:])
#     if (check(set1)):
#         print(k, 1)
#         # break
#     if (check(set2)):
#         print(k, 2)
#     if (check(set1) and check(set2)):
#         print(k)
#         break